﻿#pragma once

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

#include <thread>
#include <mutex>

#include <time.h>
#include <assert.h>
#include <cstdio>

#ifdef _WIN32
	#include <windows.h>
#elif
	// linux
#endif // DEBUG


using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024; // 最大字节数
static const size_t NFREELIST = 208;        // 最大桶数
static const size_t NPAGES = 129;           // page cache里的最大页数(桶数)
static const size_t PAGE_SHIFT = 13;        // 页数的转换，一页 = 8kb = 2^13 

// 1.在32位下，一个进程地址空间是2^32，每页定8kb(2^13)，所以页数= 2^32 /2^13 = 2^19页
// 在64位下，页数= 2^64 /2^13 = 2^51页
// 所以在64位下不能用size_t
// 2.在_WIN32配置下，_WIN32有定义，_WIN64没有定义
// 在x64配置下，_WIN32和_WIN64都有定义
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#else _WIN32
	typedef size_t PAGE_ID;
#endif

// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	// << 有乘的效果， << 13 相当于*8kb
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}


// 获取到内存对象头部的4/8个字节，返回引用，可以进行写入
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

// 管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		assert(obj);

		// 头插
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;

		_size++;
	}
	void PushRange(void* start, void* end, size_t n)
	{
		// 把一段范围内存挂到桶里
		NextObj(end) = _freeList;
		_freeList = start;

		_size += n;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		 assert(n >= _size);
		start = _freeList;
		end = start;

		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	void* Pop()
	{
		assert(_freeList);

		// 头删
		void* obj = _freeList;
		_freeList = NextObj(obj);
		_size--;

		return obj;
	}
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t& MaxSize()
	{
		return _maxSize;
	}
	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1; 
	size_t _size = 0;
};

// 计算对象大小的对齐映射规则
class SizeClass
{
public:
	// 为什么至少是8字节对齐？
	// 因为如果是在64位下，地址大小是8字节，，最起码要存得下下一块内存的地址
	
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]               8byte对齐           freelist[0,16)    128 % 8 = 16个桶
	// [128+1,1024]          16byte对齐          freelist[16,72)   (1024 - 128) % 16 = 56个桶
	// [1024+1,8*1024]       128byte对齐         freelist[72,128)
	// [8*1024+1,64*1024]    1024byte对齐        freelist[128,184)
	// [64*1024+1,256*1024]  8*1024byte对齐      freelist[184,208)

	// 对齐大小计算
	/*size_t _RoundUp(size_t size, size_t alignNum)
	{
		size_t alignSize;
		if (size % alignNum != 0)
		{
			alignSize = (size / alignNum + 1)*alignNum;
		}
		else
		{
			alignSize = size;
		}

		return alignSize;
	}*/
	static inline size_t _RoundUp(size_t bytes, size_t alignNum) // alignNum 对齐数
	{
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}

	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size < 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			// 大于256KB,同样以8K对齐
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}

	/*size_t _Index(size_t bytes, size_t alignNum)
	{
	if (bytes % alignNum == 0)
	{
	return bytes / alignNum - 1;
	}
	else
	{
	return bytes / alignNum;
	}
	}*/
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	// 计算映射的在哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) 
		{
			return _Index(bytes, 3); // 2的次方数
		}
		else if (bytes <= 1024) 
		{
			// 加上group_array[0]时因为这时已经不是从0号桶开始算了
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024) 
		{
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) 
		{
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1]
				+ group_array[0];
		}
		else if (bytes <= 256 * 1024) 
		{
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else 
		{
			assert(false);
		}
		return -1;
	}

	// 一次thread cache从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 大对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;
		return num;
	}

	// 计算一次向系统获取几个页
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size; //总的字节数 
		npage >>= PAGE_SHIFT; // 就是除以8kb，得到页数量
		if (npage == 0)
			npage = 1;
		return npage;
	}
};

// 管理多个连续页大块内存跨度结构
struct Span
{
	PAGE_ID _pageId = 0;        // 大块内存起始页的页号
	size_t _n = 0;              // 页的数量

	Span* _next = nullptr;      // 双向链表的结构
	Span* _prev = nullptr;

	size_t _objSize = 0;        // 切好的小对象的大小
	size_t _useCount = 0;       // 切好的小块内存，被分配给thread cache的计数
	void* _freeList = nullptr;  // 切好的小块内存的自由链表

	bool _isUse =false; // 是否在被使用。只要pagecache里的span被分给了central cache，就置为true
};

// 带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;

		_head->_next = _head;
		_head->_prev = _head;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;

		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;

	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		//assert(pos != _head); // 不能删除哨兵位节点

		// 条件断点
		// 查看栈帧
		if (pos == _head)
		{
			int x = 0;
		}

		Span* next = pos->_next;
		Span* prev = pos->_prev;
		prev->_next = next;
		next->_prev = prev;

		// 注意这里没有直接delete掉这块内存
		// 只是把它解链了
	}
private:
	Span* _head;
public:
	std::mutex _mtx; // thread cache里的多个线程从central cache同一个桶取出/还回内存块的桶锁
};